package minimumNumberOfVisitedCellsInAGrid_2617;

public class Solution {
    public int minimumVisitedCells(int[][] grid) {
        return process(0, 0, grid);
    }


    public int process(int i, int j, int[][] grid) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid.length) {
            return -1;
        }
        if (i == grid.length - 1 && j == grid.length - 1) {
            return 0;
        }
        int k = grid[i][j];

        if (k == 0) {
            return -1;
        }
        //横着走
        int result = -1;
        for (int i1 = 1; i1 <= k && i + i1 < grid.length; i1++) {
            int way = process(i + i1, j, grid);
            if (way == -1) {
                continue;
            }
            if (result == -1) {
                result = way;
            } else {
                result = Math.min(way, result);
            }
        }

        for (int i1 = 1; i1 <= k && j + i1 < grid.length; i1++) {
            int way = process(i, j + i1, grid);
            if (way == -1) {
                continue;
            }
            if (result == -1) {
                result = way;
            } else {
                result = Math.min(way, result);
            }
        }
        return result == -1 ? result : result + 1;
    }
}
